#pragma once
#include<vector>


void InsertSort(std::vector<int>& nums)
{
	int n = nums.size();
	for (int i = 1; i < n; i++)
	{
		int tmp = nums[i];
		int end = i - 1;
		while (end >= 0)
		{
			if (nums[end] > tmp)
			{
				nums[end+1] = nums[end];
				end--;
			}
			else
			{
				break;
			}
		}
		nums[end + 1] = tmp;
	}
}